// 魔术索引是指在数组A[0...n-1]中，满足条件A[i] = i。
// 求给定一个有序递增整数数组，编写算法找出魔术索引，
// 若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。
// 若有多个魔术索引，返回索引值最小的一个。

function findMagicIndex(nums: number[]): number {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > i) {// 对遍历的优化，如果当前值大于索引，索引可以直接跳到当前值
      i = nums[i] - 1;
      continue;
    }
    if (nums[i] === i) {
      return i;
    }
  }
  return -1;
}

// 这道题目是一道看似可以二分查找实质上不能做二分查找的问题
// 由于可能存在多个重复的数字，即便你二分搜到了满足的数字，也还是要从左依次遍历来找到最小的索引
// 也就是说就是需要On的走完整个数组才可以判断是否是最小索引
// 最简单的一次遍历就可以求解，但除此之外是还有办法可以对遍历进行优化的
// 方法就是因为题目说明有序递增整数数组，当索引 i 小于 nums[i]时，可以直接让i跳到nums[i]的位置
// 例如 nums[0]=100，那么num[0]后面的值都不会比100小
// 所以i如果还是一步步的累加，效率不高，
// 我们直接让i从100开始，因为小于100的i肯定是查找不到的
// 这里做一步优化即可。

